package com.wzh.test.graphic;

import com.sun.javafx.geom.Edge;
import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 利用【迪杰斯特拉】算法求解某一个顶点到其它顶点的最短路径
 */
public class DijkstraDemo {
    public static void main(String[] args) {
        //定义图
        Graphic graphic = new Graphic(7, Integer.MAX_VALUE);
        String[] arrVertex = {"A", "B", "C", "D", "E", "F", "G"};
        for (String vertex : arrVertex) {
            graphic.addVertex(vertex);
        }
        for (int i = 0; i < graphic.edges.length; i++) {
            for (int j = 0; j < graphic.edges[i].length; j++) {
                graphic.edges[i][j] = Integer.MAX_VALUE;
            }
        }
        graphic.addEdge("A", "B", 12);
        graphic.addEdge("A", "F", 16);
        graphic.addEdge("A", "G", 14);

        graphic.addEdge("B", "C", 10);
        graphic.addEdge("B", "F", 7);

        graphic.addEdge("C", "D", 3);
        //graphic.addEdge("C", "E", 5);
        graphic.addEdge("C", "F", 6);

        graphic.addEdge("D", "E", 4);

        graphic.addEdge("E", "F", 2);
        graphic.addEdge("E", "G", 8);
        graphic.addEdge("F", "G", 9);

        //定义起始顶点的索引为3（也就是D）
        Integer startVertexIndex = 3;
        String startVertex = graphic.vertexList.get(startVertexIndex);
        EdgeData edgeData = new EdgeData(startVertex, startVertexIndex, "", -1, 0);
        //定义一个map,存放已计算出的start点到某点的distance
        Map<Integer, EdgeData> calculatedMap = new HashMap<>();
        //定义一个优先级队列，存放将要计算的点的排队顺序
        PriorityQueue<EdgeData> queue = new PriorityQueue<>();

        queue.add(edgeData);

        while (queue.size() > 0 && calculatedMap.size() < graphic.vertexList.size()) {
            EdgeData nowEdgeData = queue.poll();
            if (!calculatedMap.containsKey(nowEdgeData.vertexIndex)) {
                calculatedMap.put(nowEdgeData.vertexIndex, nowEdgeData);

                for (int i = 0; i < graphic.vertexList.size(); i++) {
                    if(!calculatedMap.containsKey(i)) {
                        Integer weight = graphic.edges[nowEdgeData.vertexIndex][i];
                        if (weight.compareTo(Integer.MAX_VALUE) < 0) {
                            //说明链接相通
                            weight = weight + calculatedMap.get(nowEdgeData.vertexIndex).weight;
                            EdgeData newEdgeData = new EdgeData(graphic.vertexList.get(i), i, nowEdgeData.vertex, nowEdgeData.vertexIndex, weight);
                            queue.add(newEdgeData);
                        }
                    }
                }
            }
        }

        for (Integer key : calculatedMap.keySet()) {
            System.out.println(calculatedMap.get(key));
        }
    }
}

class EdgeData implements Comparable<EdgeData> {
    public String vertex;
    public Integer vertexIndex;
    public String parentVertex;
    public Integer parentVertexIndex;
    public int weight;

    public EdgeData(String vertex, Integer vertexIndex, String parentVertex, Integer parentVertexIndex, int weight) {
        this.vertex = vertex;
        this.vertexIndex = vertexIndex;
        this.parentVertex = parentVertex;
        this.parentVertexIndex = parentVertexIndex;
        this.weight = weight;
    }

    @Override
    public int compareTo(EdgeData o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return String.format("顶点%s，距离%s，父级%s", this.vertex, this.weight, this.parentVertex);
    }
}
